// 选择排序
/**
 *  算法描述：
 *   1. 在未排序的序列中找到最小（大）的元素，存放到排序序列的起始位置
 *   2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列末尾
 *   3. 重复2，直到所有排序完成
 * 
 * 
 * 复杂度：
 *  时间复杂度：O(n^2)
 *  空间复杂度：O(1)
 * 
 * 
 * 稳定性： 不稳定（选择排序算法里面包括了交换，即每次从未排序的数中选择最小的与未排序的第一个交换，破坏了相对顺序）
 * **/ 

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minValue = arr[i];
        let minIndex = i;
        for (let j = i+1; j < arr.length; j++) {
            if (arr[j] < minValue) {
                minValue = arr[j];
                minIndex = j;
            };
        };
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    };

    return arr;
};

const arr = [1, 3, 7, 4, 2, 6];

console.log(selectionSort(arr));